#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;

void inOrder(Tree *root)
{
    stack<Tree *> myStack;
    Tree *cur = root;

    while(!myStack.empty() || cur) {
        if (cur) {
            myStack.push(cur);
            cur = cur->left;
        } else {
            Tree *top = myStack.top();
            myStack.pop();
            cout << top->data << " ";
            cur = top->right;
        }
    }
}

void TreeToList(Tree *root, Tree *&head)
{
    if (!root) return;
    if (root->right) {
        TreeToList(root->right, head);
    }
    if (head) head->left = root;
    root->right = head;
    head = root;
    TreeToList(root->left, head);
}

void traverseTree(Tree *root, Tree *root2)
{
    stack<Tree *> myStack, myStack2;
    Tree *cur = root, *cur2 = root2;
    int num = 0;

    while(!myStack.empty() || cur || !myStack2.empty() || cur2) {
        if (cur) {
            myStack.push(cur);
            cur = cur->left;
        } else if (cur2) {
	    myStack2.push(cur2);
	    cur2 = cur2->left;
	} else if (!myStack.empty() && !myStack2.empty()){
            Tree *top1 = myStack.top();
            Tree *top2 = myStack2.top();
            if (top1->data < top2->data) {
		myStack.pop();
		cout << top1->data << " ";
		cur = top1->right;
	    } else {
	        myStack2.pop();
		cout << top2->data << " "; 
		cur = top2->right;
	    }
        } else if (myStack2.empty() && !myStack.empty()) {
                Tree *top1 = myStack.top();
		myStack.pop();
		cout << top1->data << " ";
		cur = top1->right;

	} else if (myStack.empty() && !myStack2.empty()) {
                Tree *top2 = myStack2.top();
	        myStack2.pop();
		cout << top2->data << " "; 
		cur = top2->right;
	}
    }
}


int main(int argc, char **argv)
{
    int input[] = {21,7,5,6,3,2,1,4,6,11,35,56};
    int input2[] = {6,23,43,54,12,54,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    int result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }

    for (int i = 0; i < sizeof(input2)/sizeof(int); i++) {
        TreeInsert(root2, input2[i]);
    }
    print_ascii_tree(root);
    print_ascii_tree(root2);
    traverseTree(root, root2);
}
